package com.cty.twentySeventhDay;

import java.util.Stack;

/*
给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

节点的左子树只包含 严格小于 当前节点的数。
节点的右子树只包含 严格大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
*/
public class Q_43 {

    // 力扣官方题解 方法一:递归
    /*
     * 思路:
     *   将当前节点的值作为左子树的上界
     *   将当前节点的值作为右子树的下界
     *   出界则返回false 否则但会true
     *   时间复杂度O(n) 空间复杂度O(n)
     * */
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    // 当前节点 上界和下界
    public boolean isValidBST(TreeNode root, Long lower, Long upper) {
        if (root == null) return true;
        if (root.val >= upper || root.val <= lower) {
            return false;
        }
        return isValidBST(root.left, lower, (long) root.val) && isValidBST(root.right, (long) root.val, upper);
    }

    // 力扣官方题解 方法二:中序遍历
    /*
    * 思路:
    *   只要是二叉搜索树中序遍历的结果一定是 顺序的 我们只需要判断
    *   先遍历当前节点的左子树 与当前节点比较 符不符合题意 符合则
    *   进行下一次遍历 不符合则返回false
    *   时间复杂度O(n) 空间复杂度O(n)
    * */
    public boolean isValidBST2(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        // 创建一个标量
        double temp = -Double.MAX_VALUE;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            if (root.val <= temp) {
                return false;
            }
            temp = root.val;
            root = root.right;
        }
        return true;
    }
}
